1. Technical Field
The present invention relates generally to integrated circuits and logic devices. In particular, the present invention pertains to an apparatus and method for Gray encoding and decoding.
2. Description of Related Art
A Gray code sequence is characterized by the fact that there is only one bit difference between any two adjacent numbers of the sequence. In contrast, in a binary code sequence, adjacent numbers may differ by several bits. Therefore, the use of Gray code avoids the transition errors or glitches caused by simultaneous transitions of multiple bits in binary code. Table 1 shows a decimal number sequence and corresponding 4-bit binary and Gray code sequences.
Note that in Table 1 the Gray code sequence is symmetric about the axis of reflection (between Gray codes 7 and 8) with the exception of the most-significant bit (G(3)).
There are many existing schemes for generating, encoding and decoding Gray code. See for example, U.S. Pat. No. 5,754,614 issued to Charles B. Guyt, for a Gray code counter; U.S. Pat. No. 5,448,606 issued to Andrew H. Snelgrove, for a Gray code counter; U.S. Pat. No. 4,618,849 issued to John H. Bruestle, also for a Gray code counter; U.S. Pat. No. 5,097,491 issued to Christopher M. Hall, for a modular Gray code counter; U.S. Pat. No. 5,164,968 issued to Kurt J. Otto, for a nine-bit Gray code generator; U.S. Pat. No. 5,426,756 issued to Jonathan Shyi and Kenny Shen, for a memory controller and method for determining the empty/full status of a FIFO memory using Gray code counters; and U.S. Pat. No. 5,084,841 issued to Williams et al. for a programmable Status flag generator FIFO using Gray code.
As used throughout this disclosure, L refers to the length of a binary code sequence being Gray encoded. Similarly, N is defined as the bit number of the binary code to be Gray encoded.
Gray encoders convert binary code (B) to corresponding Gray code (G). Let G(Nxe2x88x921) . . . G(0) denote a code word for an N-bit gray code number, and let B(Nxe2x88x921) . . . B(0) denote a code word for the corresponding binary number, where the indexes 0 and Nxe2x88x921 denote the least and most significant bits respectively. Then, the ith bit G(i) can be obtained from the corresponding binary bits as follows:
G(Nxe2x88x921)=B(Nxe2x88x921)xe2x80x83xe2x80x83(Eq. 1(a))
G(i)=B(i)XOR B(i+1) 0xe2x89xa6ixe2x89xa6Nxe2x88x922xe2x80x83xe2x80x83(Eq. 1(b))
Where the operation XOR is the Boolean operation of exclusive or for the operands between which it is positioned, defined as: 0 XOR 0=0, 1 XOR 1=0, 1 XOR 0=1, 0 XOR 1=1. FIG. 1 shows an example of the prior art logic, called a Gray encoder, to implement the above encoding procedure.
Gray decoders convert Gray code numbers to corresponding binary code numbers. Again, let G(Nxe2x88x921) . . . G(0) denote a code word for an N-bit gray code number, and let B(Nxe2x88x921) . . . B(0) denote the code word for the corresponding binary number, where the indices 0 and Nxe2x88x921 denote the least and most significant bits, respectively. The ith bit B(i) can be obtained as follows:
B(Nxe2x88x921)=G(Nxe2x88x921)xe2x80x83xe2x80x83(Eq. 2(a))
B(i)=B(i+1)XOR G(i) 0xe2x89xa6ixe2x89xa6Nxe2x88x922xe2x80x83xe2x80x83(Eq. 2(b))
FIG. 2 shows an example of the logic, called a gray decoder, to implement the above decoding procedure.
The disadvantage of prior art Gray encoders/decoders is that they only operate on full-length binary code sequences. A full-length binary code sequence is defined as an N-digit binary code where the length (L) is equal to two to the power N:
L=2N
As an example of this full-length limitation, if the memory size needed for FIFO memory control logic is 18, the bit number N for the address bus has to be at least 5 (24xe2x89xa618xe2x89xa625). However, with N=5, the L=2N limitation for prior art Gray encoders/decoders requires that the memory size be 32, nearly twice the memory required by the memory control logic.
In view of the foregoing, it can be appreciated that a need exists for a Gray encoder/decoder that can encode/decode Gray code sequences that have lengths less than 2N.
The present invention includes a method of Gray encoding/decoding between Gray code sequences, that are of even length less than or equal to 2N that are symmetrical about an axis of reflection with the exception of the most significant bit, and binary code sequences.
The present invention further includes a method of Gray encoding/decoding between N-bit binary code sequences, that have any length less than or equal to 2N, and (N+1)-bit Gray code sequences that have a length of 2*L.
Because the above methods enable the Gray encoding/decoding of binary code sequences that are less than full length, the method of the present invention results in a geometrically reduced storage requirement over the prior art.
The present invention additionally comprises a method for generating Gray Code sequences of even length less than 2N where N is the bit number and which are symmetrical about an axis of reflection with the exception of the most-significant bit.